The Pauline epistle we know as "Ephesians" was certainly written by Paul but not to the church in Ephesus. The phrase "in Ephesus" in 1:1 is not found in some of the older manuscripts. But even without that evidence, this would be a strange letter for Paul to write to the Ephesian church where he had spent three years (Acts 20:31). It's lacking in personal greetings to any of the believers there and it is written from someone who speaks about having "heard about your faith" (1:15) rather than seeing it firsthand like Paul did.

The character of Tychicus links this letter with Colossians and Philemon since he is mentioned as the bearer of each of these letters. (He seemed to frequently act as a messenger for Paul. See ACT 20:4; EPH 6:21; COL 4:7; 2TI 4:12; TIT 3:12) And it is in the book of Colossians that we discover the true recipients of "Ephesians." Paul writes:

After this letter has been read to you, see that it is also read in the church of the Laodiceans and that you in turn read the letter from Laodicea. (Col. 4:16, NIV)

Laodicea was the nearest major city between Ephesus and Colossae. Paul wrote Ephesians to the Laodiceans because of the reports he had heard about their faith and to encourage them as Gentile believers. He expected the believers in both locations to "read each other's mail."

In 2 Timothy 4:12, Paul mentions sending Tychicus to Ephesus. I wonder if he was carrying a letter?